package com.kehao.leetcode.hard.backtracking;

import org.junit.Test;

public class IsMatchSolution {
    public boolean isMatch(String s, String p) {
        boolean dp[][] = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int i = 1; i < p.length()+1; i++) {
            if(p.charAt(i-1)!='*'){
                break;
            }
            dp[0][i] = true;
        }
        for (int i = 1; i < s.length()+1; i++) {
            dp[i][0] = false;
        }
        for (int i = 1; i < s.length()+1; i++) {
            for (int j = 1; j < p.length()+1; j++) {
                if(p.charAt(j-1)=='*'){
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }else if(p.charAt(j-1)=='?'){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    if(p.charAt(j-1)==s.charAt(i-1)) {
                        dp[i][j] = dp[i-1][j-1];
                    }else {
                        dp[i][j] = false;
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }

    @Test
    public void test01(){
        String s = "aa";
        String p = "a";
        System.out.println(isMatch(s,p));
    }

    @Test
    public void test02(){
        String s = "aa";
        String p = "*";
        System.out.println(isMatch(s,p));
    }

    @Test
    public void test03(){
        String s = "cb";
        String p = "?a";
        System.out.println(isMatch(s,p));
    }

    @Test
    public void test04(){
        String s = "adceb";
        String p = "*a*b";
        System.out.println(isMatch(s,p));
    }

    @Test
    public void test05(){
        String s = "acdcb";
        String p = "a*c?b";
        System.out.println(isMatch(s,p));
    }





}
